// 7 快速排序
// 7.3 快速排序的随机化版本

use rand::random_range;

pub fn randomized_quick_sort<T: PartialOrd + Clone>(a: &mut [T], low: usize, high: usize) {
    if low < high {
        let pivot = randomized_partition(a, low, high);
        randomized_quick_sort(a, low, pivot - 1);
        randomized_quick_sort(a, pivot + 1, high);
    }
}

fn randomized_partition<T: PartialOrd + Clone>(a: &mut [T], low: usize, high: usize) -> usize {
    let r = random_range(low..high + 1);
    a.swap(r, high);
    partition(a, low, high)
}

fn partition<T: PartialOrd + Clone>(a: &mut [T], low: usize, high: usize) -> usize {
    let pivot = a[high].clone();
    let mut i: isize = low as isize - 1;
    for j in low..high {
        if a[j] <= pivot {
            i += 1;
            a.swap(i as usize, j);
        }
    }
    a.swap((i + 1) as usize, high);
    (i + 1) as usize
}

#[cfg(test)]
mod tests {

    use super::*;

    #[test]
    fn test_randomized_quick_sort() {
        use crate::test_utils;
        let mut a = test_utils::gen_random_vec::<i32>(100);
        let high = a.len() - 1;
        randomized_quick_sort(&mut a, 0, high);
        test_utils::assert_vec_asc(&a);
    }

    #[test]
    fn test_randomized_quick_sort2() {
        let mut a = [5, 2, 4, 6, 1, 3];
        let high = a.len() - 1;
        randomized_quick_sort(&mut a, 0, high);
        assert_eq!(a, [1, 2, 3, 4, 5, 6]);
    }
}
